In a cloud computing environment, a data center may include multiple networked computing devices. Some or all of the computing devices (i.e., hosts) may each run a number of virtual machines (VMs). Tenants may reserve one or more VMs, for example, to execute applications. A tenant may be a user, organization or the like that owns (e.g., pays for) the right to use the VMs. A particular tenant's VMs may be consolidated on a single computing device/host or distributed across multiple computing devices/hosts in the data center. A tenant may configure its VMs to communicate between themselves, for example, to provide a unified service of the tenant. A tenant's VM(s) may communicate with VMs of other tenants as well. A tenant may desire to know minimum communication specifications (e.g., bandwidth guarantees) between its VMs, and with VMs of other tenants, such that the tenant may determine lower bounds on the performance of the tenant's applications and/or service.